<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/7/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/7/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/25/230/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/25/230/" itemprop="url">PAT A1003</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-25T15:57:03+00:00">
                2017-02-25
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.</p>
<p>Input</p>
<p>Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (&lt;= 500) - the number of cities (and the cities are numbered from 0 to N-1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.</p>
<p>Output</p>
<p>For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.<br>All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.</p>
<p>Sample Input<br>5 6 0 2<br>1 2 1 5 3<br>0 1 1<br>0 2 2<br>0 3 1<br>1 2 1<br>2 4 1<br>3 4 1<br>Sample Output<br>2 4</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">const int MAXV = 510;//最大顶点数</span><br><span class="line">const int INF = 1000000000;//无穷大</span><br><span class="line">//n为顶点数，m为边数，st和ed分别起点和终点</span><br><span class="line">//G为邻接矩阵，weight为点权</span><br><span class="line">//d[]记录最短距离，w[]记录最大点权之和，num[]记录最短路径条数</span><br><span class="line">int n, m, st, ed, G[MAXV][MAXV], weight[MAXV];</span><br><span class="line">int d[MAXV], w[MAXV], num[MAXV];</span><br><span class="line">bool vis[MAXV] = &#123;false&#125;;//vis[i]==true表示顶点i已访问，初始均为false</span><br><span class="line"></span><br><span class="line">void Dijstra(int s)&#123;//s为起点</span><br><span class="line">    fill(d, d + MAXV, INF);</span><br><span class="line">    memset(num, 0, sizeof(num));</span><br><span class="line">    memset(w, 0, sizeof(w));</span><br><span class="line">    d[s] = 0;//s到s的距离是0</span><br><span class="line">    w[s] = weight[s];</span><br><span class="line">    num[s] = 1;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;//循环n次</span><br><span class="line">        int u = -1, MIN = INF;//u使d[u]最小，MIN存放该最小的d[u]</span><br><span class="line">        for (int j = 0; j &lt; n; j++) &#123;//找到未访问的顶点中d[]最小的</span><br><span class="line">            if (vis[j] == false &amp;&amp; d[j] &lt; MIN) &#123;</span><br><span class="line">                u = j;</span><br><span class="line">                MIN = d[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        //找不到小于INF的d[u]，说明剩下的顶点和起点s不连通</span><br><span class="line">        if (u == -1) return;</span><br><span class="line">        vis[u] = true;//标记u为已访问</span><br><span class="line">        for (int v = 0; v &lt; n; v++) &#123;</span><br><span class="line">            //如果v未访问&amp;&amp;u能到达v&amp;&amp;以u为中介点可以使d[v]更优</span><br><span class="line">            if (vis[v] == false &amp;&amp; G[u][v] != INF)&#123;</span><br><span class="line">                if (d[u] + G[u][v] &lt; d[v]) &#123;//以u为中介点时能令d[v]变小</span><br><span class="line">                    d[v] = d[u] + G[u][v];//覆盖d[v]</span><br><span class="line">                    w[v] = w[u] + weight[v];//覆盖w[v]</span><br><span class="line">                    num[v] = num[u];//覆盖num[v]</span><br><span class="line">                &#125;else if (d[u] + G[u][v] == d[v])&#123;//找到一条相同长度的路径</span><br><span class="line">                    if (w[u] + weight[v] &gt; w[v]) &#123;//以u为中介点时点权之和更大</span><br><span class="line">                        w[v] = w[u] + weight[v];//w[v]继承自w[u]</span><br><span class="line">                    &#125;</span><br><span class="line">                    //注意最短路径条数与点权无关，必须写在外面</span><br><span class="line">                    num[v] += num[u];</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d%d&quot;, &amp;n, &amp;m, &amp;st, &amp;ed);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;weight[i]);//读入点权</span><br><span class="line">    &#125;</span><br><span class="line">    int u, v;</span><br><span class="line">    fill(G[0], G[0] + MAXV * MAXV, INF);//初始化图G</span><br><span class="line">    for (int i = 0; i &lt; m; i ++)&#123;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;u, &amp;v);</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;G[u][v]);//读入边权</span><br><span class="line">        G[v][u] = G[u][v];</span><br><span class="line">    &#125;</span><br><span class="line">    Dijstra(st);//dijstra算法入口</span><br><span class="line">    printf(&quot;%d %d\n&quot;, num[ed], w[ed]);//最短距离条数，最短路径中的最大点权</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>此题在最短路径的基础上增加了点权和最短路径条数<br>一般来讲会有三种出题方式：<br>1、增加边权 2、增加点权 3、求最短路径条数<br>这三种都是在d[u] + G[u][v] == d[v]的条件下判断<br>其中前两种类似于<br>c[v] = c[u] + cost[u][v];<br>w[v] = w[u] + weight[v];<br>后一种增加num[],初始化时令num[s] = 1;其余均为0；<br>当在条件出现的时候，num[v] += num[u];</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/227/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/227/" itemprop="url">PAT A1021</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T19:34:00+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.</p>
<p>Output Specification:</p>
<p>For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print “Error: K components” where K is the number of connected components in the graph.</p>
<p>Sample Input 1:<br>5<br>1 2<br>1 3<br>1 4<br>2 5<br>Sample Output 1:<br>3<br>4<br>5<br>Sample Input 2:<br>5<br>1 3<br>1 4<br>2 5<br>3 4<br>Sample Output 2:<br>Error: 2 components<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int N = 10010;</span><br><span class="line">vector&lt;int&gt; G[N];//邻接表</span><br><span class="line">vector&lt;int&gt; deepestRoot, ans;</span><br><span class="line">bool vis[N] = &#123;false&#125;;//标记顶点i是否已经被访问</span><br><span class="line">int n, maxDepth = -1;</span><br><span class="line"></span><br><span class="line">//dfs遍历v所在的连通块</span><br><span class="line">void dfs(int v,int depth)&#123;</span><br><span class="line">    if (depth &gt; maxDepth) &#123;</span><br><span class="line">        maxDepth = depth;</span><br><span class="line">        deepestRoot.clear();</span><br><span class="line">        deepestRoot.push_back(v);</span><br><span class="line">        </span><br><span class="line">    &#125;else if(depth == maxDepth)&#123;</span><br><span class="line">        deepestRoot.push_back(v);</span><br><span class="line">    &#125;</span><br><span class="line">    vis[v] = true;//v点被访问</span><br><span class="line">    for (int i = 0; i &lt; G[v].size(); i++) &#123;</span><br><span class="line">        if (vis[G[v][i]] == false) &#123;//如果顶点G[v][i]未被访问</span><br><span class="line">            dfs(G[v][i], depth + 1);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int block = 0;</span><br><span class="line">void dfstrave()&#123;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        if (vis[i] == false) &#123;</span><br><span class="line">            dfs(i, 0);</span><br><span class="line">            block++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 1; i &lt;= n - 1; i++) &#123;</span><br><span class="line">        int a, b;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;a, &amp;b);</span><br><span class="line">        G[a].push_back(b);</span><br><span class="line">        G[b].push_back(a);</span><br><span class="line">    &#125;</span><br><span class="line">    dfstrave();</span><br><span class="line">    memset(vis, false, sizeof(vis));</span><br><span class="line">    set&lt;int&gt; sRoot;</span><br><span class="line">    if (block == 1) &#123;//是树</span><br><span class="line">        for (int i = 0 ; i &lt; deepestRoot.size(); i++) &#123;</span><br><span class="line">            sRoot.insert(deepestRoot[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        dfs(deepestRoot[0], 0);</span><br><span class="line">        for (int i = 0 ; i &lt; deepestRoot.size(); i++) &#123;</span><br><span class="line">                sRoot.insert(deepestRoot[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        set&lt;int&gt;::iterator it = sRoot.begin();</span><br><span class="line">        for (; it != sRoot.end() ; it++) &#123;</span><br><span class="line">            printf(&quot;%d\n&quot;, *it);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;Error: %d components\n&quot;, block);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>并查集版本（算法笔记）：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br></pre></td><td class="code"><pre><span class="line">    #include &quot;stdio.h&quot;</span><br><span class="line">    #include &quot;math.h&quot;</span><br><span class="line">    #include &quot;string.h&quot;</span><br><span class="line">    #include &quot;iostream&quot;</span><br><span class="line">    //#include &quot;stdlib.h&quot;</span><br><span class="line">    #include &quot;vector&quot;</span><br><span class="line">    #include &quot;set&quot;</span><br><span class="line">    #include &quot;map&quot;</span><br><span class="line">    //#include &quot;stack&quot;</span><br><span class="line">    #include &quot;queue&quot;</span><br><span class="line">    #include &quot;algorithm&quot;</span><br><span class="line">    using namespace std;</span><br><span class="line">    </span><br><span class="line">    const int N = 110;</span><br><span class="line">    vector&lt;int&gt; G[N];//邻接表</span><br><span class="line">    </span><br><span class="line">    bool isRoot[N];//记录每个结点是否作为某个集合的根结点</span><br><span class="line">    int father[N];//并查集</span><br><span class="line">    int findFather(int x)&#123;</span><br><span class="line">        int a = x;</span><br><span class="line">        while (x != father[x]) &#123;</span><br><span class="line">            x = father[x];</span><br><span class="line">        &#125;</span><br><span class="line">        //路径压缩</span><br><span class="line">        while (a != father[a]) &#123;</span><br><span class="line">            int z = a;</span><br><span class="line">            a = father[a];</span><br><span class="line">            father[z] = x;</span><br><span class="line">        &#125;</span><br><span class="line">        return x;</span><br><span class="line">    &#125;</span><br><span class="line">    void Union(int a, int b) &#123;//合并a和b所在的集合</span><br><span class="line">        int faA = findFather(a);</span><br><span class="line">        int faB = findFather(b);</span><br><span class="line">        if (faA != faB) &#123;</span><br><span class="line">            father[faA] = faB;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    void init(int n)&#123;//并查集初始化</span><br><span class="line">        for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">            father[i] = i;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int calBlock(int n)&#123;//计算连通块个数</span><br><span class="line">        int Block = 0;</span><br><span class="line">        for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">            isRoot[findFather(i)] = true;//i的根节点是findFather(i)</span><br><span class="line">        &#125;</span><br><span class="line">        for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">            Block += isRoot[i];//累加根结点个数</span><br><span class="line">        &#125;</span><br><span class="line">        return Block;</span><br><span class="line">    &#125;</span><br><span class="line">    int maxH = 0;//最大高度</span><br><span class="line">    vector&lt;int&gt; temp, ans;//temp临时存放dfs的最远结点结果，ans保存答案</span><br><span class="line">    </span><br><span class="line">    //dfs函数,u为当前访问结点编号，height为当前树高，pre为u的父节点</span><br><span class="line">    void dfs(int u, int height, int pre)&#123;</span><br><span class="line">        if (height &gt; maxH) &#123;//获得了更大的树高</span><br><span class="line">            temp.clear();//清空temp</span><br><span class="line">            temp.push_back(u);//将当前结点u加入temp中</span><br><span class="line">            maxH = height;//更新最大树高</span><br><span class="line">        &#125;else if(height == maxH)&#123;</span><br><span class="line">            temp.push_back(u);//加入当前结点到temp中</span><br><span class="line">        &#125;</span><br><span class="line">        for (int i = 0; i &lt; G[u].size(); i++) &#123;//遍历u的所有子节点</span><br><span class="line">            //由于邻接表中存放无向图，因此需要跳过回去的边</span><br><span class="line">            if (G[u][i] == pre) continue;</span><br><span class="line">            dfs(G[u][i], height + 1, u);//访问子节点</span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    int main()&#123;</span><br><span class="line">        int a, b, n;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">        init(n);</span><br><span class="line">        for (int i = 1; i &lt; n; i++) &#123;</span><br><span class="line">            scanf(&quot;%d%d&quot;, &amp;a, &amp;b);</span><br><span class="line">            G[a].push_back(b);//边a-&gt;b</span><br><span class="line">            G[b].push_back(a);//边b-&gt;a</span><br><span class="line">            Union(a, b);//合并a和b所在的集合</span><br><span class="line">        &#125;</span><br><span class="line">        int Block = calBlock(n);//计算集合数目</span><br><span class="line">        if (Block != 1) &#123;//不止一个连通块</span><br><span class="line">            printf(&quot;Error: %d components\n&quot;, Block);</span><br><span class="line">        &#125; else &#123;</span><br><span class="line">            dfs(1, 1, -1);//从1号结点开始dfs，初始高度为1</span><br><span class="line">            ans = temp;//temp为集合A，赋值给ans</span><br><span class="line">            dfs(ans[0], 1, -1);//从任意一个根节点开始遍历</span><br><span class="line">            for (int i = 0; i &lt; temp.size(); i++) &#123;</span><br><span class="line">                ans.push_back(temp[i]);//此时temp为集合b，将其加到ans中</span><br><span class="line">            &#125;</span><br><span class="line">            sort(ans.begin(), ans.end());//按编号从小到大排序</span><br><span class="line">            printf(&quot;%d\n&quot;, ans[0]);</span><br><span class="line">            for (int i = 1; i &lt; ans.size(); i++) &#123;</span><br><span class="line">                if (ans[i] != ans[i - 1]) &#123;//重复编号不输出</span><br><span class="line">                    printf(&quot;%d\n&quot;, ans[i]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">//        dfs(1, 1, -1);//从1号结点开始dfs，初始高度为1</span><br><span class="line">//        set&lt;int&gt; setofRoot;</span><br><span class="line">//        for (int i = 0; i &lt; temp.size(); i++) &#123;</span><br><span class="line">//            setofRoot.insert(temp[i]);</span><br><span class="line">//        &#125;</span><br><span class="line">//        dfs(temp[0], 1, -1);</span><br><span class="line">//        for (int i = 0; i &lt; temp.size(); i++) &#123;</span><br><span class="line">//            setofRoot.insert(temp[i]);</span><br><span class="line">//        &#125;</span><br><span class="line">//        for (set&lt;int&gt;::iterator it = setofRoot.begin(); it != setofRoot.end(); it++) &#123;</span><br><span class="line">//            printf(&quot;%d\n&quot;, *it);</span><br><span class="line">//        &#125;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">        return 0;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure></p>
<p>注释中是用集合实现deepest root的储存</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/226/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/226/" itemprop="url">PAT A1013</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T19:16:12+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.</p>
<p>For example, if we have 3 cities and 2 highways connecting city1-city2 and city1-city3. Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2-city3.</p>
<p>Input</p>
<p>Each input file contains one test case. Each case starts with a line containing 3 numbers N (&lt;1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.</p>
<p>Output</p>
<p>For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.</p>
<p>Sample Input<br>3 2 3<br>1 2<br>1 3<br>1 2 3<br>Sample Output<br>1<br>0<br>0<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int N = 1111;</span><br><span class="line">vector&lt;int&gt; G[N];//邻接表</span><br><span class="line">bool vis[N];//标记顶点i是否已经被访问</span><br><span class="line">int currentPoint;</span><br><span class="line">//dfs遍历v所在的连通块</span><br><span class="line">void dfs(int v)&#123;</span><br><span class="line">    if (v == currentPoint)  return;</span><br><span class="line">    vis[v] = true;//v点被访问</span><br><span class="line">    for (int i = 0; i &lt; G[v].size(); i++) &#123;</span><br><span class="line">        if (vis[G[v][i]] == false) &#123;//如果顶点G[v][i]未被访问</span><br><span class="line">            dfs(G[v][i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int n, m, k;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;m, &amp;k);</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        int a, b;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;a, &amp;b);//输入边的两个结点</span><br><span class="line">        G[a].push_back(b);</span><br><span class="line">        G[b].push_back(a);</span><br><span class="line">    &#125;</span><br><span class="line">    for (int query = 0; query &lt; k; query++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;currentPoint);//欲删除的顶点编号</span><br><span class="line">        memset(vis, false, sizeof(vis));</span><br><span class="line">        int block = 0;</span><br><span class="line">        for (int i = 1; i &lt;= n; i++) &#123;//枚举每个顶点</span><br><span class="line">            if (i != currentPoint &amp;&amp; vis[i] == false) &#123;//如果未被删除且未被访问</span><br><span class="line">                dfs(i);</span><br><span class="line">                block++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;%d\n&quot;, block - 1);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/225/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/225/" itemprop="url">PAT A1076</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T18:43:23+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive integers: N (&lt;=1000), the number of users; and L (&lt;=6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format:</p>
<p>M[i] user_list[i]</p>
<p>where M[i] (&lt;=100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that are followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space.</p>
<p>Then finally a positive K is given, followed by K UserID’s for query.</p>
<p>Output Specification:</p>
<p>For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can triger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.</p>
<p>Sample Input:<br>7 3<br>3 2 3 4<br>0<br>2 5 6<br>2 3 1<br>2 3 4<br>1 4<br>1 5<br>2 2 6<br>Sample Output:<br>4<br>5<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int MAXV = 1010;</span><br><span class="line">struct Node&#123;</span><br><span class="line">    int id;</span><br><span class="line">    int layer;</span><br><span class="line">&#125;;</span><br><span class="line">vector&lt;Node&gt; Adj[MAXV];//邻接表</span><br><span class="line">bool inq[MAXV] = &#123;false&#125;;//顶点是否已被加入过队列</span><br><span class="line">int BFS(int s, int L)&#123;//start为起始结点，L为层数上限</span><br><span class="line">    int numForward = 0;//转发数</span><br><span class="line">    queue&lt;Node&gt; q;</span><br><span class="line">    Node start;</span><br><span class="line">    start.id = s;</span><br><span class="line">    start.layer = 0;</span><br><span class="line">    q.push(start);</span><br><span class="line">    inq[s] = true;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        Node topNode = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        int u = topNode.id;</span><br><span class="line">        for (int i = 0; i &lt; Adj[u].size(); i++) &#123;</span><br><span class="line">            Node next = Adj[u][i];//从u出发能到达的结点next</span><br><span class="line">            next.layer = topNode.layer + 1;//next的层号等于当前结点层号加1</span><br><span class="line">            //如果next的编号未被加入过队列，且next的层次不超过上限L</span><br><span class="line">            if (inq[next.id] == false &amp;&amp; next.layer &lt;= L) &#123;</span><br><span class="line">                q.push(next);</span><br><span class="line">                inq[next.id] = true;</span><br><span class="line">                numForward++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return numForward;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    Node user;</span><br><span class="line">    int n, L, numFollow, idFollow;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;L);//结点个数，层数上限</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        user.id = i;//用户编号为i</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;numFollow);//i用户关注的人数</span><br><span class="line">        for (int j = 1; j &lt;= numFollow; j++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;idFollow);</span><br><span class="line">            Adj[idFollow].push_back(user);//idFollow-&gt;i 被i用户关注</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int numQuery, s;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;numQuery);</span><br><span class="line">    for (int i = 0; i &lt; numQuery; i++) &#123;</span><br><span class="line">        memset(inq, false, sizeof(inq));//inq数组初始化</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;s);</span><br><span class="line">        int numForward = BFS(s, L);//BFS,返回转发数</span><br><span class="line">        printf(&quot;%d\n&quot;, numForward);//输出转发数</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/224/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/224/" itemprop="url">PAT A1034</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T18:34:13+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:</p>
<p>Name1 Name2 Time</p>
<p>where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.</p>
<p>Output Specification:</p>
<p>For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.</p>
<p>Sample Input 1:<br>8 59<br>AAA BBB 10<br>BBB AAA 20<br>AAA CCC 40<br>DDD EEE 5<br>EEE DDD 70<br>FFF GGG 30<br>GGG HHH 20<br>HHH FFF 10<br>Sample Output 1:<br>2<br>AAA 3<br>GGG 3<br>Sample Input 2:<br>8 70<br>AAA BBB 10<br>BBB AAA 20<br>AAA CCC 40<br>DDD EEE 5<br>EEE DDD 70<br>FFF GGG 30<br>GGG HHH 20<br>HHH FFF 10<br>Sample Output 2:<br>0</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 2010;//总人数</span><br><span class="line">const int INF = 1000000000;//无穷大</span><br><span class="line"></span><br><span class="line">map&lt;int, string&gt; intToString;//编号-&gt;姓名</span><br><span class="line">map&lt;string, int&gt; stringToInt;//姓名-&gt;编号</span><br><span class="line">map&lt;string, int&gt; Gang;//head-&gt;人数</span><br><span class="line">int G[maxn][maxn] = &#123;0&#125;, weight[maxn] = &#123;0&#125;;//邻接矩阵G，点权weight</span><br><span class="line">int n, k, numPerson = 0;//边数n, 下限k, 总人数numPerson</span><br><span class="line">bool vis[maxn] = &#123;false&#125;;//标记是否被访问</span><br><span class="line"></span><br><span class="line">//DFS函数访问单个连通块，nowVisit为当前访问的编号</span><br><span class="line">//head为头目，numMember为成员编号，totoalValue为连通块的总边权</span><br><span class="line">void DFS(int nowVisit, int&amp; head, int&amp; numMember, int&amp; totalValue)&#123;</span><br><span class="line">    numMember++;//成员人数加1</span><br><span class="line">    vis[nowVisit] = true;//标记nowVisit已访问</span><br><span class="line">    if (weight[nowVisit] &gt; weight[head]) &#123;</span><br><span class="line">        head = nowVisit;//换老大了</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; numPerson; i++) &#123;//枚举所有人</span><br><span class="line">        if (G[nowVisit][i] &gt; 0) &#123;//如果从nowVisit能达到i</span><br><span class="line">            totalValue += G[nowVisit][i];//连通块的总边权增加该边权</span><br><span class="line">            G[nowVisit][i] = G[i][nowVisit] = 0;//删除这条边，防止回头</span><br><span class="line">            if (vis[i] == false) &#123;</span><br><span class="line">                DFS(i, head, numMember, totalValue);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">//DFSTrave函数遍历整个图，获取每个连通块的信息</span><br><span class="line">void DFSTrave()&#123;</span><br><span class="line">    for (int i = 0; i &lt; numPerson; i++) &#123;//枚举所有人</span><br><span class="line">        if (vis[i] == false) &#123;</span><br><span class="line">            int head = i, numMember = 0, totalValue = 0;//头目、成员数目，总边权</span><br><span class="line">            DFS(i, head, numMember, totalValue);</span><br><span class="line">            if (numMember &gt; 2 &amp;&amp; totalValue &gt; k) &#123;</span><br><span class="line">                //head人数为numMember</span><br><span class="line">                Gang[intToString[head]] = numMember;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">//change函数返回姓名str对应的编号</span><br><span class="line">int change(string str)&#123;</span><br><span class="line">    if (stringToInt.find(str) != stringToInt.end()) &#123;//如果str已经出现过</span><br><span class="line">        return stringToInt[str];</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        stringToInt[str] = numPerson;//str的编号为strPerson</span><br><span class="line">        intToString[numPerson] = str;//建立对应关系</span><br><span class="line">        return numPerson++;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    int w;</span><br><span class="line">    string str1, str2;</span><br><span class="line">    cin &gt;&gt; n &gt;&gt; k;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        cin &gt;&gt; str1 &gt;&gt; str2 &gt;&gt; w;//输入两个边的端点和点权</span><br><span class="line">        int id1 = change(str1);</span><br><span class="line">        int id2 = change(str2);</span><br><span class="line">        weight[id1] += w;</span><br><span class="line">        weight[id2] += w;</span><br><span class="line">        G[id1][id2] += w;</span><br><span class="line">        G[id2][id1] += w;</span><br><span class="line">    &#125;</span><br><span class="line">    DFSTrave();//遍历整个图所有连通块，获取gang的信息</span><br><span class="line">    cout &lt;&lt; Gang.size() &lt;&lt; endl;//gang的个数</span><br><span class="line">    map&lt;string, int&gt;::iterator it;</span><br><span class="line">    for (it = Gang.begin(); it != Gang.end(); it++) &#123;//遍历所有gang</span><br><span class="line">        cout &lt;&lt; it-&gt;first &lt;&lt; &quot; &quot; &lt;&lt; it-&gt;second &lt;&lt;endl;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/220/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/220/" itemprop="url">PAT A1098 . Insertion or Heap Sort (25)</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T12:40:00+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A “social cluster” is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.</p>
<p><strong>Input Specification:</strong></p>
<p>Each input file contains one test case. For each test case, the first line contains a positive integer N (&lt;=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:</p>
<p>Ki: hi[1] hi[2] … hi[Ki]</p>
<p>where Ki (&gt;0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].</p>
<p><strong>Output Specification:</strong></p>
<p>For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.</p>
<p><strong>Sample Input:</strong><br>8<br>3: 2 7 10<br>1: 4<br>2: 5 3<br>1: 4<br>1: 3<br>1: 4<br>4: 6 8 1 5<br>1: 4<br><strong>Sample Output:</strong><br>3<br>4 3 1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn= 1010;</span><br><span class="line">int father[maxn];//存放父亲结点</span><br><span class="line">int isRoot[maxn] = &#123;0&#125;;//记录每个结点是否作为某个集合的根结点</span><br><span class="line">int course[maxn] = &#123;0&#125;;//记录喜欢活动h的任意一个人的编号</span><br><span class="line">int findFather(int x)&#123;//查找x所在集合的根节点</span><br><span class="line">    int a = x;</span><br><span class="line">    while (x != father[x]) &#123;</span><br><span class="line">        x = father[x];</span><br><span class="line">    &#125;</span><br><span class="line">    //路径压缩</span><br><span class="line">    while (a != father[a]) &#123;</span><br><span class="line">        int z = a;</span><br><span class="line">        a = father[a];</span><br><span class="line">        father[z] = x;</span><br><span class="line">    &#125;</span><br><span class="line">    return x;</span><br><span class="line">&#125;</span><br><span class="line">void Union(int a, int b)&#123;//合并a和b所在的集合</span><br><span class="line">    int faA = findFather(a);</span><br><span class="line">    int faB = findFather(b);</span><br><span class="line">    if (faA != faB) &#123;</span><br><span class="line">        father[faA] = faB;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void init(int n)&#123;//初始化father[i]为i，且isRoot[i]为false</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        father[i] = i;</span><br><span class="line">        isRoot[i] = 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">bool cmp(int a, int b)&#123;</span><br><span class="line">    return a &gt; b;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, k, h;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    init(n);</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d:&quot;, &amp;k);</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;//对每个活动</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;h);</span><br><span class="line">            if (course[h] == 0) &#123;//h活动第一次有人喜欢</span><br><span class="line">                course[h] = i;//记录那个人的名字</span><br><span class="line">            &#125;</span><br><span class="line">            Union(i, findFather(course[h]));//合并</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        isRoot[findFather(i)]++;</span><br><span class="line">    &#125;</span><br><span class="line">    int ans = 0;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        if (isRoot[i]) &#123;</span><br><span class="line">            ans++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, ans);</span><br><span class="line">    sort(isRoot + 1, isRoot + n + 1, cmp);</span><br><span class="line">    for (int i = 1; i &lt;= ans; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, isRoot[i]);</span><br><span class="line">        if (i &lt; ans) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/219/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/219/" itemprop="url">PAT A1107 . Social Clusters</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T10:34:00+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A “social cluster” is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.</p>
<p><strong>Input Specification:</strong></p>
<p>Each input file contains one test case. For each test case, the first line contains a positive integer N (&lt;=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:</p>
<p>Ki: hi[1] hi[2] … hi[Ki]</p>
<p>where Ki (&gt;0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].</p>
<p><strong>Output Specification:</strong></p>
<p>For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.</p>
<p><strong>Sample Input:</strong><br>8<br>3: 2 7 10<br>1: 4<br>2: 5 3<br>1: 4<br>1: 3<br>1: 4<br>4: 6 8 1 5<br>1: 4<br><strong>Sample Output:</strong><br>3<br>4 3 1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn= 1010;</span><br><span class="line">int father[maxn];//存放父亲结点</span><br><span class="line">int isRoot[maxn] = &#123;0&#125;;//记录每个结点是否作为某个集合的根结点</span><br><span class="line">int course[maxn] = &#123;0&#125;;//记录喜欢活动h的任意一个人的编号</span><br><span class="line">int findFather(int x)&#123;//查找x所在集合的根节点</span><br><span class="line">    int a = x;</span><br><span class="line">    while (x != father[x]) &#123;</span><br><span class="line">        x = father[x];</span><br><span class="line">    &#125;</span><br><span class="line">    //路径压缩</span><br><span class="line">    while (a != father[a]) &#123;</span><br><span class="line">        int z = a;</span><br><span class="line">        a = father[a];</span><br><span class="line">        father[z] = x;</span><br><span class="line">    &#125;</span><br><span class="line">    return x;</span><br><span class="line">&#125;</span><br><span class="line">void Union(int a, int b)&#123;//合并a和b所在的集合</span><br><span class="line">    int faA = findFather(a);</span><br><span class="line">    int faB = findFather(b);</span><br><span class="line">    if (faA != faB) &#123;</span><br><span class="line">        father[faA] = faB;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void init(int n)&#123;//初始化father[i]为i，且isRoot[i]为false</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        father[i] = i;</span><br><span class="line">        isRoot[i] = 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">bool cmp(int a, int b)&#123;</span><br><span class="line">    return a &gt; b;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, k, h;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    init(n);</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d:&quot;, &amp;k);</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;//对每个活动</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;h);</span><br><span class="line">            if (course[h] == 0) &#123;//h活动第一次有人喜欢</span><br><span class="line">                course[h] = i;//记录那个人的名字</span><br><span class="line">            &#125;</span><br><span class="line">            Union(i, findFather(course[h]));//合并</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        isRoot[findFather(i)]++;</span><br><span class="line">    &#125;</span><br><span class="line">    int ans = 0;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        if (isRoot[i]) &#123;</span><br><span class="line">            ans++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, ans);</span><br><span class="line">    sort(isRoot + 1, isRoot + n + 1, cmp);</span><br><span class="line">    for (int i = 1; i &lt;= ans; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, isRoot[i]);</span><br><span class="line">        if (i &lt; ans) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/24/218/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/24/218/" itemprop="url">好朋友 - 并查集</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-24T10:30:49+00:00">
                2017-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/笔记/" itemprop="url" rel="index">
                    <span itemprop="name">笔记</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>输入格式<br>    输入的第一行有两个正整数n &lt;=100 和m &lt;= 100，分别表示数码宝贝的个数和好朋友的组数，其中数码宝贝的编号为1~n。<br>    接下来有m行，每行两个正整数a和b，表示数码宝贝a和数码宝贝b是好朋友<br>输出格式<br>    输出一个整数，表示这些数码宝贝可以分成的组数。</p>
<p>样例输入1<br>4 2<br>1 4<br>2 3<br>样例输出1<br>2<br>样例输入2<br>7 5<br>1 2<br>2 3<br>3 1<br>1 4<br>5 6<br>样例输出2<br>3<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn= 110;</span><br><span class="line">int father[maxn];//存放父亲结点</span><br><span class="line">bool isRoot[maxn];//记录每个结点是否作为某个集合的根结点</span><br><span class="line">int findFather(int x)&#123;//查找x所在集合的根节点</span><br><span class="line">    int a = x;</span><br><span class="line">    while (x != father[x]) &#123;</span><br><span class="line">        x = father[x];</span><br><span class="line">    &#125;</span><br><span class="line">    //路径压缩</span><br><span class="line">    while (a != father[a]) &#123;</span><br><span class="line">        int z = a;</span><br><span class="line">        a = father[a];</span><br><span class="line">        father[z] = x;</span><br><span class="line">    &#125;</span><br><span class="line">    return x;</span><br><span class="line">&#125;</span><br><span class="line">void Union(int a, int b)&#123;//合并a和b所在的集合</span><br><span class="line">    int faA = findFather(a);</span><br><span class="line">    int faB = findFather(b);</span><br><span class="line">    if (faA != faB) &#123;</span><br><span class="line">        father[faA] = faB;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void init(int n)&#123;//初始化father[i]为i，且isRoot[i]为false</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        father[i] = i;</span><br><span class="line">        isRoot[i] = false;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, m, a, b;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);</span><br><span class="line">    init(n);</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;a, &amp;b);</span><br><span class="line">        Union(a, b);</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        isRoot[findFather(i)] = true;</span><br><span class="line">    &#125;</span><br><span class="line">    int ans = 0;//记录集合数目</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        ans += isRoot[i];</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d&quot;, ans);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/216/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/216/" itemprop="url">PAT A1066</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T19:47:36+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.<br><img src="https://www.patest.cn/upload/79_mtxjq1kj3gx.jpg" alt="请输入图片描述"><br><img src="https://www.patest.cn/upload/79_mtxjqnwja2o.jpg" alt="请输入图片描述"><br><img src="https://www.patest.cn/upload/79_mtxjr4gyzdg.jpg" alt="请输入图片描述"><br><img src="https://www.patest.cn/upload/79_mtxjrh51o9y.jpg" alt="请输入图片描述"><br>Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print ythe root of the resulting AVL tree in one line.</p>
<p>Sample Input 1:<br>5<br>88 70 61 96 120<br>Sample Output 1:<br>70<br>Sample Input 2:<br>7<br>88 70 61 96 120 90 65<br>Sample Output 2:<br>88</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">struct node &#123;</span><br><span class="line">    int v, height;//v为结点权值，height为当前子树高度</span><br><span class="line">    node *lchild,*rchild;</span><br><span class="line">&#125; *root, *null;</span><br><span class="line"></span><br><span class="line">//生成一个新结点，v为结点权值</span><br><span class="line">node* newNode(int v)&#123;</span><br><span class="line">    node* Node = new node;</span><br><span class="line">    Node-&gt;v = v;</span><br><span class="line">    Node-&gt;height = 1;</span><br><span class="line">    Node-&gt;lchild = Node-&gt;rchild = NULL;</span><br><span class="line">    return Node;</span><br><span class="line">&#125;</span><br><span class="line">//获取以root为根的子树当前的高度height</span><br><span class="line">int getHeight(node* root)&#123;</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        return 0;</span><br><span class="line">    &#125;</span><br><span class="line">    return root-&gt;height;</span><br><span class="line">&#125;</span><br><span class="line">//更新结点root的height</span><br><span class="line">void updateHeight(node* root)&#123;</span><br><span class="line">    //max+1</span><br><span class="line">    root-&gt;height = max(getHeight(root-&gt;lchild), getHeight(root-&gt;rchild)) + 1;</span><br><span class="line">&#125;</span><br><span class="line">//计算结点root的平衡因子</span><br><span class="line">int getBalance(node* root)&#123;</span><br><span class="line">    return getHeight(root-&gt;lchild) - getHeight(root-&gt;rchild);</span><br><span class="line">&#125;</span><br><span class="line">//左旋</span><br><span class="line">void L(node* &amp;root)&#123;</span><br><span class="line">    node* temp = root-&gt;rchild;</span><br><span class="line">    root-&gt;rchild = temp-&gt;lchild;</span><br><span class="line">    temp-&gt;lchild = root;</span><br><span class="line">    updateHeight(root);</span><br><span class="line">    updateHeight(temp);</span><br><span class="line">    root = temp;</span><br><span class="line">&#125;</span><br><span class="line">//右旋</span><br><span class="line">void R(node* &amp;root)&#123;</span><br><span class="line">    node* temp = root-&gt;lchild;</span><br><span class="line">    root-&gt;lchild = temp-&gt;rchild;</span><br><span class="line">    temp-&gt;rchild = root;</span><br><span class="line">    updateHeight(root);</span><br><span class="line">    updateHeight(temp);</span><br><span class="line">    root = temp;</span><br><span class="line">&#125;</span><br><span class="line">//插入权值为v的结点</span><br><span class="line">void insert(node* &amp;root, int v)&#123;</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        root = newNode(v);</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    if (v &lt; root-&gt;v) &#123;</span><br><span class="line">        insert(root-&gt;lchild, v);//往左子树插入</span><br><span class="line">        updateHeight(root);</span><br><span class="line">        if (getBalance(root) == 2) &#123;</span><br><span class="line">            if (getBalance(root-&gt;lchild) == 1) &#123;//LL</span><br><span class="line">                R(root);</span><br><span class="line">            &#125;else if(getBalance(root-&gt;lchild) == -1)&#123;//LR</span><br><span class="line">                L(root-&gt;lchild);</span><br><span class="line">                R(root);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        insert(root-&gt;rchild, v);//往右子树插入</span><br><span class="line">        updateHeight(root);</span><br><span class="line">        if (getBalance(root) == -2) &#123;</span><br><span class="line">            if (getBalance(root-&gt;rchild) == -1) &#123;//RR</span><br><span class="line">                L(root);</span><br><span class="line">            &#125;else if(getBalance(root-&gt;rchild) == 1)&#123;//RL</span><br><span class="line">                R(root-&gt;rchild);</span><br><span class="line">                L(root);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, v;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0 ; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;v);</span><br><span class="line">        insert(root, v);</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, root-&gt;v);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/215/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/215/" itemprop="url">PAT A1099</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T18:50:19+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:</p>
<p>The left subtree of a node contains only nodes with keys less than the node’s key.<br>The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.<br>Both the left and right subtrees must also be binary search trees.<br>Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format “left_index right_index”, provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.</p>
<p>Sample Input:<br>9<br>1 6<br>2 3<br>-1 -1<br>-1 4<br>5 -1<br>-1 -1<br>7 -1<br>-1 8<br>-1 -1<br>73 45 11 58 82 25 67 38 42<br>Sample Output:<br>58 25 82 11 38 67 45 73 42<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 110;</span><br><span class="line">int n;</span><br><span class="line">struct node&#123;</span><br><span class="line">    int data;</span><br><span class="line">    int left, right;</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">int number[maxn], num = 0;</span><br><span class="line">void inOrder(int root)&#123;</span><br><span class="line">    if (root == -1) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    inOrder(Node[root].left);</span><br><span class="line">    Node[root].data = number[num++];</span><br><span class="line">    inOrder(Node[root].right);</span><br><span class="line">&#125;</span><br><span class="line">void levelOrder(int root)&#123;</span><br><span class="line">    queue&lt;int&gt; q;</span><br><span class="line">    q.push(root);</span><br><span class="line">    num = 0;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        int now = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        num++;</span><br><span class="line">        printf(&quot;%d&quot;, Node[now].data);</span><br><span class="line">        if (num &lt; n) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">        if (Node[now].left != -1) &#123;</span><br><span class="line">            q.push(Node[now].left);</span><br><span class="line">        &#125;</span><br><span class="line">        if (Node[now].right != -1) &#123;</span><br><span class="line">            q.push(Node[now].right);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d %d&quot;, &amp;Node[i].left, &amp;Node[i].right);</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;number[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(number, number + n);//从小到大排序</span><br><span class="line">    inOrder(0);</span><br><span class="line">    levelOrder(0);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/6/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/6/">6</a><span class="page-number current">7</span><a class="page-number" href="/page/8/">8</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/8/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
